package com.liunian.test;

import java.util.LinkedList;
import java.util.List;

public class FindItinerary332 {

	/**
	 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

	 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

	 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
	 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
	 */
	LinkedList<String> res = new LinkedList<>();
	public List<String> findItinerary(List<List<String>> tickets) {
		tickets.sort((a, b) -> a.get(1).compareTo(b.get(1)));
		res.add("JFK");
		boolean[] used = new boolean[tickets.size()];
		backTracking(tickets, used);
		return res;
	}

	private boolean backTracking(List<List<String>> tickets, boolean[] used) {
		if (tickets.size() + 1 == res.size()) {
			return true;
		}
		for (int i = 0; i < tickets.size(); i++) {
			if (i > 0 && tickets.get(i).equals(tickets.get(i - 1)) && !used[i - 1]) {
				continue;
			}
			if (!used[i] && tickets.get(i).get(0).equals(res.getLast())) {
				used[i] = true;
				res.add(tickets.get(i).get(1));
				if (backTracking(tickets, used)) {
					return true;
				}
				used[i] = false;
				res.removeLast();
			}
		}
		return false;
	}

}
